
from operator import attrgetter

import numpy as np
import networkx as nx

from gauss import gauss_jordan_independent
from circuit import Circuit

def get_circuits(graph, mark_middle_vertice=False):
	set_weights(graph)
	ac_circuits = get_arc_short_circuits(graph, mark_middle_vertice)
	bidir_edges = get_bidir_edges(graph)
	circuits = ac_circuits + bidir_edges
	circuits.sort(key = attrgetter("weight"))
	return circuits

def get_arc_short_circuits(graph, mark_middle_vertice=False):
	edges = graph.edges()
	edges.sort()			# edges() seem to produce sorted edges, but it isn't explicitely stated in doc
	nodes = graph.nodes()
	shortest_paths = get_shortest_paths(graph)
	circuits = []
	for edge in edges:
		x = edge[0]
		y = edge[1]
		for z in nodes:
			if (z != x) and (z != y) and (z in shortest_paths[y]) and (x in shortest_paths[z]):
					path_yz = shortest_paths[y][z]
					path_zx = shortest_paths[z][x]
					n_common_vertices = len(set(path_yz).intersection(set(path_zx)))
					if n_common_vertices > 1:	# paths can only have 'z' in common
						continue
					#print "Circuit:"
					#print edge
					#print path_yz
					#print path_zx
					path_yz_noz = path_yz[0:len(path_yz) - 1]
					path_zx_nox = path_zx[0:len(path_zx) - 1]
					full_path = [x] + path_yz_noz + path_zx_nox
					if mark_middle_vertice:
						circuit = Circuit(full_path, graph, z)
					else:
						circuit = Circuit(full_path, graph)

					if not circuit in circuits:
						circuits.append(circuit)
	circuits.sort(key = attrgetter("weight"))
	return circuits

def get_bidir_edges(graph):
	edges = graph.edges()
	edges.sort()
	bidir_edges = []
	ignored_edges = [] 
	for edge in edges:
		if edge in ignored_edges:
			continue
		contr_edge = (edge[1], edge[0])
		if contr_edge in edges:
			bidir_edges.append(Circuit([edge[0], edge[1]], graph))
			ignored_edges.append(contr_edge)
	bidir_edges.sort(key = attrgetter("weight"))
	return bidir_edges

def set_weights(graph):
	edges = graph.edges()
	n_edges = len(edges)
	if n_edges == 0:
		return
	epsilon = 0.5 / (n_edges * len(graph.nodes()))
	perturbance_mod = get_perturbance_mod(n_edges, epsilon)
	index = 0
	for edge in edges:
		perturbance = (3 ** (-index)) * epsilon - perturbance_mod
		weight = 1
		graph[edge[0]][edge[1]]['weight'] = weight
		perturbed_weight = weight + perturbance
		graph[edge[0]][edge[1]]['perturbed_weight'] = perturbed_weight
		index = index + 1

def get_perturbance_mod(n_edges, epsilon):
	# original perturbance proposed: epsilon * (1/3)^index, epsilon < 1 / (n_edges * n_nodes)
	orig_perturbances_sum = epsilon * (1.0 - 3 ** (-n_edges)) / (1 - 1.0 / 3)	# sum of n elements of geometric sequence
	orig_min_edge_weight = 1							# TODO modify, if edges weights are to be added to program
	if orig_perturbances_sum >= orig_min_edge_weight:	# if >=, it can affect potentially Dijkstra algorithm
		diff = orig_perturbances_sum - orig_min_edge_weight
		perturbance_mod = 2.0 * diff / n_edges
	else:
		perturbance_mod = 0
	return perturbance_mod

def get_shortest_paths(graph):
	# beware, a_p_d_p() will accept an invalid attribute name and choose randomly...
	return nx.all_pairs_dijkstra_path(graph, None, "perturbed_weight")

def r_greedy(circuits, eiti_mod=False, debug=False, graph=None):
	if not circuits:
		return ([], [])
	if debug:
		edges = graph.edges()
		edges.sort()
	else:
		edges = None
	circuits.sort(key = attrgetter("weight"))
	b_less = []
	relevant = []
	prev_circuit = circuits[0]
	r_equal = [prev_circuit]
	b_equal = [prev_circuit]
	for circuit in circuits[1:]:
		if debug:
			print("\n-----  CIRCUIT processed:  -----")
			print(circuit)
			print("\nB< (min base)")
			print(b_less)
			print("\nR (relevant circuits)")
			print(relevant)
			print("\nB= :")
			print(b_equal)
			print("\nR= :")
			print(r_equal)
		if (eiti_mod):
			# modification of algorithm by program authors
			if circuit.weight > prev_circuit.weight:
				relevant.extend(r_equal)
				b_less.extend(b_equal)
				r_equal = []
				b_equal = []
				if debug:
					print("\nnew B< (min base)")
					print(b_less)
					print("\nnew R (relevant circuits)")
					print(relevant)
					print("\nnew B= :")
					print(b_equal)
					print("\nnew R= :")
					print(r_equal)
			if debug:
				print('\ncheck independent(circuit, B<)')
			if independent([circuit] + b_less, debug, edges):
				if debug:
					print "(circuit, B<) are INDEPENDENT"
				r_equal.append(circuit)
			if debug:
				print('\ncheck independent(circuit, B<, B=)')
			if independent([circuit] + b_less + b_equal, debug, edges):
				if debug:
					print "(circuit, B<, B=) are INDEPENDENT"
				b_equal.append(circuit)
		else:
			# original Gleiss algorithm
			if circuit.weight > prev_circuit.weight:
				relevant.extend(r_equal)
				b_less.extend(b_equal)
				r_equal = [circuit]
				b_equal = [circuit]
				if debug:
					print("\nnew B< (min base)")
					print(b_less)
					print("\nnew R (relevant circuits)")
					print(relevant)
					print("\nnew B= :")
					print(b_equal)
					print("\nnew R= :")
					print(r_equal)
			else:
				if debug:
					print('\ncheck independent(circuit, B<)')
				if independent([circuit] + b_less, debug, edges):
					if debug:
						print "(circuit, B<) are INDEPENDENT"
					r_equal.append(circuit)
				if debug:
					print('\ncheck independent(circuit, B<, B=)')
				if independent([circuit] + b_less + b_equal, debug, edges):
					if debug:
						print "(circuit, B<, B=) are INDEPENDENT"
					b_equal.append(circuit)
		prev_circuit = circuit
	relevant.extend(r_equal)
	b_less.extend(b_equal)
	return (b_less, relevant)

def independent(circuits, debug=False, edges=None):
	matrix = np.matrix(circuits[0].binary_vector)
	for circuit in circuits[1:]:
		matrix = np.vstack([matrix, circuit.binary_vector])
	if debug:
		print(' '),
		for edge in edges:
			print("%s:%s" % (str(edge[0]), str(edge[1]))),
		print('')
	ind = gauss_jordan_independent(matrix, debug)
	return ind

